package 栈;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

import java.util.Stack;

/**
 * 题目：
 * 给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *  示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 */
public class 直方图最大矩形面积 {
    class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack<Integer> stack = new Stack<Integer>();
            stack.push(-1);
            int max = 0;
            for (int i = 0; i < heights.length; i++) {
                while(stack.peek() !=-1 &&heights[stack.peek()] >= heights[i]) {
                    int height = heights[stack.pop()];
                    int width = i - stack.peek()-1;
                    max = Math.max(max, height * width);
                }
                stack.push(i);
            }
            while (stack.peek() != -1) {
                int height = heights[stack.pop()];
                int width = heights.length - stack.peek() - 1;
                max = Math.max(max, height * width);
            }

            return max;

        }
    }
}
